import org.junit.jupiter.api.Test;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _22_括号生成 {
    @Test
    public void test(){
        System.out.println(generateParenthesis(2));
    }

    /**
     * 思路：每个位置的括号都有两种情况，所以可以抽象成二叉树，我们使用深度优先遍历得出所有的组合
     * 然后对不符合要去的进行剪枝，当left的数量大于n的时候，以及right的数量大于left的时候就需要剪枝了
     * 剪完枝，就需要进行回溯，就是直接return；
     * @param n
     * @return
     */
    public List<String> generateParenthesis(int n) {
        ArrayList<String > list=new ArrayList<>();
        dfs(n,"",list,0,0);
        return list;
    }

    public void dfs(int n,String path,List<String > res ,int left,int right){
        //进行剪枝
        if (left>n||right>left) return;
        if (path.length()==2*n){
            //递归结束的条件
            res.add(path);
            return;
        }
        //遍历左子树，就是两种情况的一种“（”
        dfs(n,path+"(",res,left+1,right);
        //遍历右子树，就是两种情况的一种“）”
        dfs(n,path+")",res,left,right+1);
    }
}
